'''
https://leetcode.cn/problems/making-a-large-island/
'''

from typing import List


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def infect(i, j, id):
            if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:
                grid[i][j] = id
                infect(i + 1, j, id)
                infect(i - 1, j, id)
                infect(i, j + 1, id)
                infect(i, j - 1, id)

        id = 2
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    infect(i, j, id)
                    id += 1
        for row in grid:
            print(row)
        count = [0] * id
        for i in range(m):
            for j in range(n):
                if grid[i][j] > 1:
                    count[grid[i][j]] += 1
        ans = max(count)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    s = set()
                    v = 1
                    for a, b in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                        to_x = i + a
                        to_y = j + b
                        if 0 <= to_x < m and 0 <= to_y < n and grid[to_x][to_y] not in s:
                            v += count[grid[to_x][to_y]]
                            s.add(grid[to_x][to_y])
                    ans = max(ans, v)
        return ans


grid = [
    [1, 1, 0, 0, 1, 1, 1, 0],
    [1, 1, 0, 0, 1, 1, 1, 0],
    [1, 1, 1, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 0, 0, 0],
    [1, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 0, 0, 1, 0, 0, 0],
    [0, 1, 1, 1, 0, 1, 1, 1],
    [0, 0, 0, 0, 1, 0, 0, 0],
]
print(Solution().largestIsland(grid))
